class Solution {
public:
    bool isMatch(string s, string p) {
        //方法1：递归
		/*if(p.empty())
            return s.empty();
        if(p.size()==1)
        {
            return (s.size()==1 && (s[0]==p[0] || p[0]=='.'));
        }
        else if(p[1] != '*')
        {
            if(s.empty())
                return false;
            return (s[0]==p[0] || p[0]=='.') && isMatch(s.substr(1), p.substr(1));
        }
        else
        {
            return isMatch(s, p.substr(2)) || (!s.empty() && (s[0]==p[0] || p[0]=='.') && isMatch(s.substr(1), p));
        }*/
		//方法二：动态规划
        int m=s.size(), n=p.size();
        vector<vector<int>>dp(m+1, vector<int>(n+1, false));
        dp[0][0]=true;
        for(int i=0; i<=m; ++i)
        {
            for(int j=1; j<=n; ++j)
            {
                if(j>1 && p[j-1]=='*')
                {
                    dp[i][j] = dp[i][j-2] || (i>0 && (s[i-1]==p[j-2] || p[j-2]=='.') && dp[i-1][j]);
                }
                else
                {
                    dp[i][j]= i>0 && dp[i-1][j-1] && (s[i-1]==p[j-1] || p[j-1]=='.');
                }
            }
        }
        return dp[m][n];
    }
};